/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 * 买卖股票的最佳时机
 * @param prices 
 */
export const maxProfit = (prices: number[]): number => {
    // dp[i] = 在i天前买进的最小值
    // i天前买进的最小值, 和当前值相比较, 如果小于等于当前值, 那么还是dp[i], 否则更新dp[i]为当前值
    // 然后更新当前的当前的最大值, 当前值 - dp[i]

    const len = prices.length;
    let min = prices[0]

    // 在i天卖出的最大值
    let ans = 0;
    for (let i = 1; i < len; i++) {
        if (prices[i] < min) {
            // 更新最小值, 不用更新最大值
            min = prices[i]
        } else {
            // 更新最大值
            ans = Math.max(ans, prices[i] - min)
        }
    }
    return ans;

};

// 动态规划
const maxProfit3 = (prices: number[]): number => {
    // dp[i] = 在i天前买进的最小值
    // 动态转移方程为: dp[i] = min{dp[i - 1], prices[i]}
    // i天前买进的最小值, 和当前值相比较, 如果小于等于当前值, 那么还是dp[i], 否则更新dp[i]为当前值
    // 然后更新当前的当前的最大值, 当前值 - dp[i]
    const len = prices.length;
    const dp: number[] = new Array(len)

    // 在i天卖出的最大值
    let ans = 0;

    dp[0] = prices[0] // dp初始值
    for (let i = 1; i < len; i++) {
        dp[i] = Math.min(dp[i - 1], prices[i])

        // 更新最大值
        ans = Math.max(prices[i] - dp[i], ans)
    }
    return ans;

};

// 暴力法
const maxProfit2 = (prices: number[]): number => {
    const len = prices.length;

    // 最大利润
    let max = 0;

    for (let i = 0; i < len; i++) {
        let cur = prices[i]
        // 比较cur和后面的值的大小
        for (let j = i + 1; j < len; j++) {
            max = Math.max(prices[j] - cur, max)
        }
    }

    return max
};

console.log(maxProfit([7, 1, 5, 3, 6, 4]))